package com.demo.java.OD451_500.OD474;

import java.util.*;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【启动多任务排序(C&D卷)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146354182
 */
public class OdMain {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取输入数据
        List<String> inputList = new ArrayList<>();
        while (scanner.hasNextLine()) {
            String line = scanner.nextLine().trim();
            if (line.isEmpty()) {
                break;
            }
            inputList.add(line);
        }

        // 邻接表：存储任务的依赖关系
        Map<String, List<String>> neighborDic = new HashMap<>();
        // 入度表：存储每个任务的入度（即依赖它的前置任务数量）
        Map<String, Integer> indegreeDic = new HashMap<>();

        // 解析输入数据并构建任务依赖关系
        for (String input : inputList) {
            String[] parts = input.split("->");
            String fromTask = parts[0].trim();  // 前置任务
            String[] toTasks = parts[1].split(" ");  // 可能有多个后续任务

            // 确保前置任务存在于入度表
            indegreeDic.putIfAbsent(fromTask, 0);

            // 处理多个后续任务
            for (String toTask : toTasks) {
                toTask = toTask.trim();

                // 确保后续任务的入度表存在
                indegreeDic.putIfAbsent(toTask, 0);

                // 记录依赖关系
                neighborDic.computeIfAbsent(fromTask, k -> new ArrayList<>()).add(toTask);

                // 增加后续任务的入度
                indegreeDic.put(toTask, indegreeDic.get(toTask) + 1);
            }
        }

        // 记录入度为 0 的任务（即可以立即执行的任务）
        List<String> availableTasks = new ArrayList<>();

        for (String task : indegreeDic.keySet()) {
            if (indegreeDic.get(task) == 0) {
                availableTasks.add(task);
            }
        }

        // 按字典序排序
        Collections.sort(availableTasks);

        // BFS 队列
        Queue<String> queue = new LinkedList<>(availableTasks);

        // 记录拓扑排序结果
        List<String> result = new ArrayList<>();

        // 执行拓扑排序
        while (!queue.isEmpty()) {
            String currentTask = queue.poll();
            result.add(currentTask);

            // 处理当前任务的后续任务
            if (neighborDic.containsKey(currentTask)) {
                List<String> nextTasks = neighborDic.get(currentTask);

                // 对当前任务的后续任务进行字典排序
                Collections.sort(nextTasks);

                // 处理每个后续任务
                for (String nextTask : nextTasks) {
                    // 减少入度
                    indegreeDic.put(nextTask, indegreeDic.get(nextTask) - 1);

                    // 如果入度变为 0，加入队列
                    if (indegreeDic.get(nextTask) == 0) {
                        queue.add(nextTask);
                    }
                }
            }
        }

        // 输出排序后的任务列表
        System.out.println(String.join(" ", result));

        scanner.close();
    }
}
